package _go

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	//根节点为空 直接返回nil
	if root == nil {
		return nil
	}

	//有一个是根节点直接返回根节点
	if root == q || root == p {
		return root
	}

	//后续遍历
	Left := lowestCommonAncestor(root.Left, p, q)
	Right := lowestCommonAncestor(root.Right, p, q)

	//后续遍历类似从下向上 所以都不是nil的情况下 结果为root
	if Left != nil && Right != nil {
		return root
	}
	//如果都为nil说明不在书里面
	if Left == nil && Right == nil {
		return nil
	}

	//左节点为空返回右节点
	if Left == nil {
		return Right
	} else {
		return Left
	}
}
